package leetcode.code295;

import java.util.PriorityQueue;

public class MedianFinder extends Solution295 {

	private PriorityQueue<Integer> min;
	private int minSize;
	private PriorityQueue<Integer> max;
	private int maxSize;

	public MedianFinder() {
		min = new PriorityQueue<>((o1, o2) -> o1 - o2);
		max = new PriorityQueue<>((o1, o2) -> o2 - o1);
	}

	@Override
	public void addNum(int num) {
		if (minSize == 0) {
			min.add(num);
			minSize++;
			return;
		}
		int minHead = min.peek();
		if (num > minHead) {
			min.add(num);
			minSize++;
		} else {
			max.add(num);
			maxSize++;
		}
		if (minSize - maxSize == 2) {
			max.add(min.poll());
			minSize--;
			maxSize++;
		} else if (maxSize - minSize == 2) {
			min.add(max.poll());
			minSize++;
			maxSize--;
		}
	}

	@Override
	public double findMedian() {
		if (minSize - maxSize == 0) {
			return (max.peek() + min.peek()) / 2.0;
		}
		if (minSize - maxSize == 1) {
			return min.peek();
		}
		if (maxSize - minSize == 1) {
			return max.peek();
		}
		return 0;
	}

	public static void main(String[] args) {
		MedianFinder medianFinder = new MedianFinder();
//		medianFinder.debug1();
		medianFinder.debug2();
	}

}
